<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <title>剑指offer第一周 - Even - A super concise theme for Hugo</title>
  <meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">


<meta name="author" content="olOwOlo" /><meta name="description" content="找出数组中重复的数字 题意 思路 桶排序 空间复杂度O(1) 的算法 利用swap把i==nuns[i] 每次先判断出 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16" /><meta name="keywords" content="Hugo, theme, even" />






<meta name="generator" content="Hugo 0.83.1 with theme even" />


<link rel="canonical" href="https://xiongshou.github.io/post/%E7%AC%AC%E4%B8%80%E5%91%A8/" />
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/manifest.json">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">



<link href="/sass/main.min.f92fd13721ddf72129410fd8250e73152cc6f2438082b6c0208dc24ee7c13fc4.css" rel="stylesheet">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.css" integrity="sha256-7TyXnr2YU040zfSP+rEcz29ggW4j56/ujTPwjMzyqFY=" crossorigin="anonymous">


<meta property="og:title" content="剑指offer第一周" />
<meta property="og:description" content="找出数组中重复的数字 题意 思路 桶排序 空间复杂度O(1) 的算法 利用swap把i==nuns[i] 每次先判断出 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://xiongshou.github.io/post/%E7%AC%AC%E4%B8%80%E5%91%A8/" /><meta property="article:section" content="post" />
<meta property="article:published_time" content="2021-06-01T20:16:50&#43;09:00" />
<meta property="article:modified_time" content="2021-06-01T20:16:50&#43;09:00" />

<meta itemprop="name" content="剑指offer第一周">
<meta itemprop="description" content="找出数组中重复的数字 题意 思路 桶排序 空间复杂度O(1) 的算法 利用swap把i==nuns[i] 每次先判断出 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"><meta itemprop="datePublished" content="2021-06-01T20:16:50&#43;09:00" />
<meta itemprop="dateModified" content="2021-06-01T20:16:50&#43;09:00" />
<meta itemprop="wordCount" content="1896">
<meta itemprop="keywords" content="剑指offer," /><meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="剑指offer第一周"/>
<meta name="twitter:description" content="找出数组中重复的数字 题意 思路 桶排序 空间复杂度O(1) 的算法 利用swap把i==nuns[i] 每次先判断出 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->

</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/" class="logo">Even</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <a href="/">
        <li class="mobile-menu-item">Home</li>
      </a><a href="/post/">
        <li class="mobile-menu-item">Archives</li>
      </a><a href="/tags/">
        <li class="mobile-menu-item">Tags</li>
      </a><a href="/categories/">
        <li class="mobile-menu-item">Categories</li>
      </a><a href="/about/">
        <li class="mobile-menu-item">About</li>
      </a>
  </ul>

  


</nav>

  <div class="container" id="mobile-panel">
    <header id="header" class="header">
        <div class="logo-wrapper">
  <a href="/" class="logo">Even</a>
</div>





<nav class="site-navbar">
  <ul id="menu" class="menu">
    <li class="menu-item">
        <a class="menu-item-link" href="/">Home</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/post/">Archives</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/tags/">Tags</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/categories/">Categories</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/about/">About</a>
      </li>
  </ul>
</nav>

    </header>

    <main id="main" class="main">
      <div class="content-wrapper">
        <div id="content" class="content">
          <article class="post">
    
    <header class="post-header">
      <h1 class="post-title">剑指offer第一周</h1>

      <div class="post-meta">
        <span class="post-time"> 2021-06-01 </span>
        <div class="post-category">
            <a href="/categories/%E5%89%91%E6%8C%87offer/"> 剑指offer </a>
            </div>
        
      </div>
    </header>

    <div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">Contents</h2>
  <div class="post-toc-content always-active">
    <nav id="TableOfContents">
  <ul>
    <li><a href="#找出数组中重复的数字">找出数组中重复的数字</a>
      <ul>
        <li><a href="#题意">题意</a></li>
        <li><a href="#思路">思路</a></li>
        <li><a href="#代码">代码</a></li>
      </ul>
    </li>
    <li><a href="#不修改数组找出重复的数字只能用o1空间">不修改数组找出重复的数字(只能用O(1)空间</a>
      <ul>
        <li><a href="#题意-1">题意</a></li>
        <li><a href="#思路-1">思路</a></li>
        <li><a href="#代码-1">代码</a></li>
      </ul>
    </li>
    <li><a href="#二维数组的查找">二维数组的查找</a>
      <ul>
        <li><a href="#题意-2">题意</a></li>
        <li><a href="#思路-2">思路</a></li>
        <li><a href="#代码-2">代码</a></li>
      </ul>
    </li>
    <li><a href="#替换空格">替换空格</a></li>
    <li><a href="#题意-3">题意</a>
      <ul>
        <li><a href="#代码-3">代码</a></li>
      </ul>
    </li>
    <li><a href="#从尾到头打印链表">从尾到头打印链表</a>
      <ul>
        <li><a href="#题意-4">题意</a></li>
        <li><a href="#代码-4">代码</a></li>
      </ul>
    </li>
    <li><a href="#重建二叉树">重建二叉树</a>
      <ul>
        <li><a href="#题意-5">题意</a></li>
        <li><a href="#思路-3">思路</a></li>
        <li><a href="#代码-5">代码</a></li>
      </ul>
    </li>
    <li><a href="#二叉树的下一个节点树的后继">二叉树的下一个节点（树的后继）</a>
      <ul>
        <li><a href="#题意-6">题意</a></li>
        <li><a href="#思路-4">思路</a></li>
        <li><a href="#代码-6">代码</a></li>
      </ul>
    </li>
    <li><a href="#用俩个栈实现队列">用俩个栈实现队列</a>
      <ul>
        <li><a href="#题意-7">题意</a></li>
        <li><a href="#思路-5">思路</a></li>
        <li><a href="#代码-7">代码</a></li>
      </ul>
    </li>
    <li><a href="#旋转数组的最小数字">旋转数组的最小数字</a>
      <ul>
        <li><a href="#题意-8">题意</a>
          <ul>
            <li></li>
          </ul>
        </li>
        <li><a href="#思路-6">思路：</a></li>
        <li><a href="#代码-8">代码</a></li>
      </ul>
    </li>
    <li><a href="#矩阵中的路径dfs找路径先st后循环">矩阵中的路径：（dfs找路径:先st，后循环）</a>
      <ul>
        <li><a href="#代码-9">代码</a></li>
      </ul>
    </li>
  </ul>
</nav>
  </div>
</div>
    <div class="post-content">
      <h1 id="找出数组中重复的数字">找出数组中重复的数字</h1>
<h2 id="题意">题意</h2>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghh81br02cj315q0ho0vq.jpg" alt="image-20200806173049290"></p>
<h2 id="思路">思路</h2>
<ol>
<li>桶排序</li>
<li>空间复杂度O(1) 的算法
<ol>
<li>利用swap把i==nuns[i]</li>
<li>每次先判断出</li>
</ol>
</li>
</ol>
<h2 id="代码">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">duplicateInArray</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">n</span><span class="o">=</span><span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">if</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&lt;</span><span class="mi">0</span> <span class="o">||</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&gt;=</span><span class="n">n</span><span class="p">)</span>
                <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">st</span><span class="p">[</span><span class="n">n</span><span class="p">];</span>
        <span class="n">memset</span><span class="p">(</span><span class="n">st</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="k">sizeof</span> <span class="n">st</span><span class="p">);</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">if</span><span class="p">(</span><span class="n">st</span><span class="p">[</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]])</span>
                <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="k">else</span> <span class="n">st</span><span class="p">[</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">++</span><span class="p">;</span>
        <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">duplicateInArray</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">n</span><span class="o">=</span><span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
        <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="nl">x</span><span class="p">:</span><span class="n">nums</span><span class="p">)</span>
            <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;</span><span class="mi">0</span> <span class="o">||</span> <span class="n">x</span><span class="o">&gt;=</span><span class="n">n</span><span class="p">)</span> 
                <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="c1">// 把下标i对应值，放到它应该去的地方
</span><span class="c1"></span>            <span class="k">while</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">!=</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]],</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
            <span class="c1">// 放完之后，判断这个位置i==nums[i]
</span><span class="c1"></span>            <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">!=</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
           
            
        <span class="p">}</span>
       
        <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="不修改数组找出重复的数字只能用o1空间">不修改数组找出重复的数字(只能用O(1)空间</h1>
<h2 id="题意-1">题意</h2>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghh85aby4wj316c0esdid.jpg" alt="image-20200806173443848"></p>
<h2 id="思路-1">思路</h2>
<p>​		数字范围是1-n公n个数，但是nums有n+1个数。说明n个坑，填n+1个数。抽屉原理，必有一个坑，有俩个数， 使用二分，找一边数的个数大与坑的数，check进去。</p>
<p>​		总思路是，将坑的序号进行二分，对一边所有坑统计数字总和进行check。若这一边坑里面的数&gt;坑的个数，那么这一边true。</p>
<p>​		注意，计算s++时候，判断数字x是不是(L,mid)</p>
<h2 id="代码-1">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">duplicateInArray</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">l</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">r</span><span class="o">=</span><span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        
        <span class="k">while</span><span class="p">(</span><span class="n">l</span><span class="o">&lt;</span><span class="n">r</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">mid</span><span class="o">=</span><span class="n">r</span><span class="o">+</span><span class="n">l</span><span class="o">&gt;&gt;</span><span class="mi">1</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">s</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="nl">x</span><span class="p">:</span><span class="n">nums</span><span class="p">)</span> 
                <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">&gt;=</span><span class="n">l</span> <span class="o">&amp;&amp;</span> <span class="n">x</span><span class="o">&lt;=</span><span class="n">mid</span><span class="p">)</span>
                    <span class="n">s</span><span class="o">++</span><span class="p">;</span>
            <span class="k">if</span><span class="p">(</span><span class="n">s</span><span class="o">&gt;</span><span class="n">mid</span><span class="o">-</span><span class="n">l</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="n">r</span><span class="o">=</span><span class="n">mid</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">l</span><span class="o">=</span><span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">r</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="二维数组的查找">二维数组的查找</h1>
<h2 id="题意-2">题意</h2>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghh8rn9087j319m0muwhs.jpg" alt="image-20200806175611879"></p>
<h2 id="思路-2">思路</h2>
<p>​		具有一种单调性：</p>
<pre><code>        * 数组中（i，j）的位置，i左边都比它小，j下边都比它大
</code></pre>
<ul>
<li>从右上角找
* 要找的数比右上角小，那么j&ndash;
<ul>
<li>要找的数比右上角大，那么i++</li>
</ul>
</li>
<li>直到找到数字</li>
<li>这个过程用while循环</li>
</ul>
<h2 id="代码-2">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">bool</span> <span class="n">searchArray</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&gt;</span> <span class="n">array</span><span class="p">,</span> <span class="kt">int</span> <span class="n">target</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span><span class="p">(</span><span class="n">array</span><span class="p">.</span><span class="n">empty</span><span class="p">())</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    
        <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">j</span><span class="o">=</span><span class="n">array</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="c1">//cout&lt;&lt;i&lt;&lt;&#39; &#39;&lt;&lt;j&lt;&lt;endl;
</span><span class="c1"></span>        <span class="k">while</span><span class="p">(</span><span class="n">i</span><span class="o">&lt;</span><span class="n">array</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&amp;&amp;</span> <span class="n">j</span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span><span class="p">(</span><span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">target</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
            <span class="k">if</span><span class="p">(</span><span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&gt;</span><span class="n">target</span><span class="p">)</span> <span class="n">j</span><span class="o">--</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">i</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="替换空格">替换空格</h1>
<h1 id="题意-3">题意</h1>
<p>水题</p>
<h2 id="代码-3">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">string</span> <span class="n">replaceSpaces</span><span class="p">(</span><span class="n">string</span> <span class="o">&amp;</span><span class="n">str</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">string</span> <span class="n">s</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="nl">x</span><span class="p">:</span><span class="n">str</span><span class="p">)</span>
            <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">==</span><span class="sc">&#39; &#39;</span><span class="p">)</span> <span class="n">s</span><span class="o">=</span><span class="n">s</span><span class="o">+</span><span class="s">&#34;%20&#34;</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">s</span><span class="o">=</span><span class="n">s</span><span class="o">+</span><span class="n">x</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">s</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="从尾到头打印链表">从尾到头打印链表</h1>
<h2 id="题意-4">题意</h2>
<p>​		逆序输出链表的值</p>
<h2 id="代码-4">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cm">/**
</span><span class="cm"> * Definition for singly-linked list.
</span><span class="cm"> * struct ListNode {
</span><span class="cm"> *     int val;
</span><span class="cm"> *     ListNode *next;
</span><span class="cm"> *     ListNode(int x) : val(x), next(NULL) {}
</span><span class="cm"> * };
</span><span class="cm"> */</span>
<span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">printListReversingly</span><span class="p">(</span><span class="n">ListNode</span><span class="o">*</span> <span class="n">head</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">res</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">head</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">res</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">head</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="n">head</span><span class="o">=</span><span class="n">head</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">reverse</span><span class="p">(</span><span class="n">res</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="n">res</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
        <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="重建二叉树">重建二叉树</h1>
<h2 id="题意-5">题意</h2>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghh91sx5tkj314c0p6gpc.jpg" alt="image-20200806180557998"></p>
<h2 id="思路-3">思路</h2>
<p>​		前序+中序确定二叉树</p>
<ul>
<li>前序遍历确定根节点</li>
<li>找到根节点，在中序遍历中确定左子树大小，右子树大小</li>
<li>快速找到前序中根节点在中序中位置：hash表</li>
<li>递归建立某一区间的二叉树
<ul>
<li>变量
<ul>
<li>前序数列，前序在这一区间的范围</li>
<li>中序数列，中序在这一区间的范围</li>
</ul>
</li>
</ul>
</li>
<li>总之：前序遍历确定根，dfs中序建立树, 递归过程中用一个变量代表左子树长度。</li>
</ul>
<h2 id="代码-5">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cm">/**
</span><span class="cm"> * Definition for a binary tree node.
</span><span class="cm"> * struct TreeNode {
</span><span class="cm"> *     int val;
</span><span class="cm"> *     TreeNode *left;
</span><span class="cm"> *     TreeNode *right;
</span><span class="cm"> *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
</span><span class="cm"> * };
</span><span class="cm"> */</span>
<span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>

    <span class="n">unordered_map</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">pos</span><span class="p">;</span>

    <span class="n">TreeNode</span><span class="o">*</span> <span class="nf">buildTree</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">preorder</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">inorder</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">preorder</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">++</span> <span class="p">)</span>
            <span class="n">pos</span><span class="p">[</span><span class="n">inorder</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">dfs</span><span class="p">(</span><span class="n">preorder</span><span class="p">,</span> <span class="n">inorder</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="n">TreeNode</span><span class="o">*</span> <span class="nf">dfs</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span><span class="n">pre</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span><span class="n">in</span><span class="p">,</span> <span class="kt">int</span> <span class="n">pl</span><span class="p">,</span> <span class="kt">int</span> <span class="n">pr</span><span class="p">,</span> <span class="kt">int</span> <span class="n">il</span><span class="p">,</span> <span class="kt">int</span> <span class="n">ir</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">pl</span> <span class="o">&gt;</span> <span class="n">pr</span><span class="p">)</span> <span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">pos</span><span class="p">[</span><span class="n">pre</span><span class="p">[</span><span class="n">pl</span><span class="p">]]</span> <span class="o">-</span> <span class="n">il</span><span class="p">;</span>
        <span class="n">TreeNode</span><span class="o">*</span> <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="n">TreeNode</span><span class="p">(</span><span class="n">pre</span><span class="p">[</span><span class="n">pl</span><span class="p">]);</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">left</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">pre</span><span class="p">,</span> <span class="n">in</span><span class="p">,</span> <span class="n">pl</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">pl</span> <span class="o">+</span> <span class="n">k</span><span class="p">,</span> <span class="n">il</span><span class="p">,</span> <span class="n">il</span> <span class="o">+</span> <span class="n">k</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">right</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">pre</span><span class="p">,</span> <span class="n">in</span><span class="p">,</span> <span class="n">pl</span> <span class="o">+</span> <span class="n">k</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">pr</span><span class="p">,</span> <span class="n">il</span> <span class="o">+</span> <span class="n">k</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">ir</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>

</code></pre></td></tr></table>
</div>
</div><h1 id="二叉树的下一个节点树的后继">二叉树的下一个节点（树的后继）</h1>
<h2 id="题意-6">题意</h2>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghhem5cwb4j30zi0p2woj.jpg" alt="image-20200806211830868"></p>
<h2 id="思路-4">思路</h2>
<ul>
<li>这颗树有右子树，
<ul>
<li>后继就是右子树的左子树的左子树的左子树</li>
</ul>
</li>
<li>没有右子树
<ul>
<li>一直往上找，找到节点是父节点的左儿子</li>
<li><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghheqq2ghdj30oe0gmacc.jpg" alt="image-20200806212255005"></li>
<li>否则 没有后继</li>
</ul>
</li>
</ul>
<h2 id="代码-6">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cm">/**
</span><span class="cm"> * Definition for a binary tree node.
</span><span class="cm"> * struct TreeNode {
</span><span class="cm"> *     int val;
</span><span class="cm"> *     TreeNode *left;
</span><span class="cm"> *     TreeNode *right;
</span><span class="cm"> *     TreeNode *father;
</span><span class="cm"> *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
</span><span class="cm"> * };
</span><span class="cm"> */</span>
<span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">TreeNode</span><span class="o">*</span> <span class="n">inorderSuccessor</span><span class="p">(</span><span class="n">TreeNode</span><span class="o">*</span> <span class="n">p</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span><span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">p</span><span class="o">=</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">right</span><span class="p">;</span>
            <span class="k">while</span><span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">p</span><span class="o">=</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">left</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">return</span> <span class="n">p</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">while</span><span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">father</span> <span class="o">&amp;&amp;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">father</span><span class="o">-&gt;</span><span class="n">right</span> <span class="o">==</span> <span class="n">p</span><span class="p">)</span>
            <span class="n">p</span><span class="o">=</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">father</span><span class="p">;</span>
         <span class="k">if</span><span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">father</span><span class="p">)</span> <span class="k">return</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">father</span><span class="p">;</span>
        <span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="用俩个栈实现队列">用俩个栈实现队列</h1>
<h2 id="题意-7">题意</h2>
<hr>
<h2 id="思路-5">思路</h2>
<p>​		每次操作很暴力的模拟</p>
<h2 id="代码-7">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span><span class="lnt">34
</span><span class="lnt">35
</span><span class="lnt">36
</span><span class="lnt">37
</span><span class="lnt">38
</span><span class="lnt">39
</span><span class="lnt">40
</span><span class="lnt">41
</span><span class="lnt">42
</span><span class="lnt">43
</span><span class="lnt">44
</span><span class="lnt">45
</span><span class="lnt">46
</span><span class="lnt">47
</span><span class="lnt">48
</span><span class="lnt">49
</span><span class="lnt">50
</span><span class="lnt">51
</span><span class="lnt">52
</span><span class="lnt">53
</span><span class="lnt">54
</span><span class="lnt">55
</span><span class="lnt">56
</span><span class="lnt">57
</span><span class="lnt">58
</span><span class="lnt">59
</span><span class="lnt">60
</span><span class="lnt">61
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">MyQueue</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/** Initialize your data structure here. */</span>
    <span class="n">stack</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">st</span><span class="p">,</span><span class="n">temp</span><span class="p">;</span>
    <span class="n">MyQueue</span><span class="p">()</span> <span class="p">{</span>
        
    <span class="p">}</span>
    
    <span class="cm">/** Push element x to the back of queue. */</span>
    <span class="kt">void</span> <span class="nf">push</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">st</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
    <span class="p">}</span>
    
    <span class="cm">/** Removes the element from in front of queue and returns that element. */</span>
    <span class="kt">int</span> <span class="nf">pop</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">while</span><span class="p">(</span><span class="n">st</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">temp</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">st</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
            <span class="n">st</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="p">}</span>
        <span class="kt">int</span> <span class="n">a</span><span class="o">=</span><span class="n">temp</span><span class="p">.</span><span class="n">top</span><span class="p">();</span>
         <span class="n">temp</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="k">while</span><span class="p">(</span><span class="n">temp</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">st</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">temp</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
            <span class="n">temp</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">a</span><span class="p">;</span>
    <span class="p">}</span>
    
    <span class="cm">/** Get the front element. */</span>
    <span class="kt">int</span> <span class="nf">peek</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">while</span><span class="p">(</span><span class="n">st</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">temp</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">st</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
            <span class="n">st</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="p">}</span>
        <span class="kt">int</span> <span class="n">a</span><span class="o">=</span><span class="n">temp</span><span class="p">.</span><span class="n">top</span><span class="p">();</span>
       
        <span class="k">while</span><span class="p">(</span><span class="n">temp</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">st</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">temp</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
            <span class="n">temp</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">a</span><span class="p">;</span>
    <span class="p">}</span>
    
    <span class="cm">/** Returns whether the queue is empty. */</span>
    <span class="kt">bool</span> <span class="nf">empty</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">st</span><span class="p">.</span><span class="n">empty</span><span class="p">();</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="cm">/**
</span><span class="cm"> * Your MyQueue object will be instantiated and called as such:
</span><span class="cm"> * MyQueue obj = MyQueue();
</span><span class="cm"> * obj.push(x);
</span><span class="cm"> * int param_2 = obj.pop();
</span><span class="cm"> * int param_3 = obj.peek();
</span><span class="cm"> * bool param_4 = obj.empty();
</span><span class="cm"> */</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="旋转数组的最小数字">旋转数组的最小数字</h1>
<h2 id="题意-8">题意</h2>
<p>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。</p>
<p>输入一个升序的数组的一个旋转，输出旋转数组的最小元素。</p>
<p>例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。</p>
<p>数组可能包含重复项。</p>
<p><strong>注意</strong>：数组内所含元素非负，若数组大小为0，请返回-1。</p>
<h4 id="样例">样例</h4>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt">1
</span><span class="lnt">2
</span><span class="lnt">3
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="err">输入：</span><span class="n">nums</span><span class="o">=</span><span class="p">[</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">]</span>

<span class="err">输出：</span><span class="mi">0</span>
</code></pre></td></tr></table>
</div>
</div><h2 id="思路-6">思路：</h2>
<p>​		是具有单调性质的，可以二分。特判一下，序列直接单调上升，直接输出答案。需要注意，包含重复项。</p>
<p><img src="https://tva1.sinaimg.cn/large/007S8ZIlly1ghhf0au65jj310m0miacs.jpg" alt="image-20200806213206688"></p>
<p>​		用while循环去掉最后那部分直线，剩下就是二分找最小值，</p>
<h2 id="代码-8">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">findMin</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span><span class="p">(</span><span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">n</span><span class="o">=</span><span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">nums</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">==</span><span class="n">nums</span><span class="p">[</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="n">n</span><span class="o">--</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">&gt;</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="kt">int</span> <span class="n">l</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">r</span><span class="o">=</span><span class="n">n</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">l</span><span class="o">&lt;</span><span class="n">r</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">mid</span><span class="o">=</span><span class="n">l</span><span class="o">+</span><span class="n">r</span><span class="o">&gt;&gt;</span><span class="mi">1</span><span class="p">;</span>
            <span class="k">if</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">mid</span><span class="p">]</span><span class="o">&lt;</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="n">r</span><span class="o">=</span><span class="n">mid</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">l</span><span class="o">=</span><span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="n">r</span><span class="p">];</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><h1 id="矩阵中的路径dfs找路径先st后循环">矩阵中的路径：（dfs找路径:先st，后循环）</h1>
<h2 id="代码-9">代码</h2>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span><span class="lnt">34
</span><span class="lnt">35
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>

  
 
    
    <span class="kt">bool</span> <span class="n">hasPath</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;&gt;&amp;</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">string</span> <span class="o">&amp;</span><span class="n">str</span><span class="p">)</span> <span class="p">{</span>
       
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">matrix</span><span class="p">.</span><span class="n">size</span><span class="p">();</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">matrix</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">size</span><span class="p">();</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
                <span class="k">if</span><span class="p">(</span><span class="n">dfs</span><span class="p">(</span><span class="n">matrix</span><span class="p">,</span><span class="n">str</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="mi">0</span><span class="p">))</span>   <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="n">dx</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span><span class="o">=</span><span class="p">{</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">},</span><span class="n">dy</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span><span class="o">=</span><span class="p">{</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">};</span>
    <span class="kt">bool</span> <span class="nf">dfs</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;&gt;&amp;</span> <span class="n">g</span><span class="p">,</span> <span class="n">string</span> <span class="o">&amp;</span><span class="n">s</span><span class="p">,</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span><span class="kt">int</span> <span class="n">b</span><span class="p">,</span><span class="kt">int</span> <span class="n">u</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">b</span><span class="p">]</span><span class="o">!=</span><span class="n">s</span><span class="p">[</span><span class="n">u</span><span class="p">])</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">u</span><span class="o">&gt;=</span><span class="n">s</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
            <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        
        <span class="kt">char</span> <span class="n">t</span><span class="o">=</span><span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">b</span><span class="p">];</span>
        <span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">b</span><span class="p">]</span><span class="o">=</span><span class="sc">&#39;*&#39;</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="mi">4</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">nx</span><span class="o">=</span><span class="n">a</span><span class="o">+</span><span class="n">dx</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="kt">int</span> <span class="n">ny</span><span class="o">=</span><span class="n">b</span><span class="o">+</span><span class="n">dy</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="k">if</span><span class="p">(</span><span class="n">nx</span><span class="o">&lt;</span><span class="mi">0</span> <span class="o">||</span> <span class="n">nx</span><span class="o">&gt;</span><span class="n">g</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">ny</span><span class="o">&lt;</span><span class="mi">0</span> <span class="o">||</span> <span class="n">ny</span><span class="o">&gt;</span><span class="n">g</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span>
           
            <span class="k">if</span><span class="p">(</span><span class="n">dfs</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">s</span><span class="p">,</span><span class="n">nx</span><span class="p">,</span><span class="n">ny</span><span class="p">,</span><span class="n">u</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
         
        <span class="p">}</span>
        <span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">b</span><span class="p">]</span><span class="o">=</span><span class="n">t</span><span class="p">;</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div>
    </div>

    <div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">Author</span>
    <span class="item-content">olOwOlo</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">LastMod</span>
    <span class="item-content">
        2021-06-01
        
    </span>
  </p>
  
  
</div>
<footer class="post-footer">
      <div class="post-tags">
          <a href="/tags/%E5%89%91%E6%8C%87offer/">剑指offer</a>
          </div>
      <nav class="post-nav">
        <a class="prev" href="/post/%E6%A0%91%E5%9B%BE%E4%B8%93%E9%A2%98/">
            <i class="iconfont icon-left"></i>
            <span class="prev-text nav-default">剑指offer图专题</span>
            <span class="prev-text nav-mobile">Prev</span>
          </a>
        <a class="next" href="/post/%E7%AC%AC7%E5%91%A8/">
            <span class="next-text nav-default">剑指offer第七周</span>
            <span class="next-text nav-mobile">Next</span>
            <i class="iconfont icon-right"></i>
          </a>
      </nav>
    </footer>
  </article>
        </div>
        

  

  

      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="social-links">
      <a href="mailto:your@email.com" class="iconfont icon-email" title="email"></a>
      <a href="http://localhost:1313" class="iconfont icon-stack-overflow" title="stack-overflow"></a>
      <a href="http://localhost:1313" class="iconfont icon-twitter" title="twitter"></a>
      <a href="http://localhost:1313" class="iconfont icon-facebook" title="facebook"></a>
      <a href="http://localhost:1313" class="iconfont icon-linkedin" title="linkedin"></a>
      <a href="http://localhost:1313" class="iconfont icon-google" title="google"></a>
      <a href="http://localhost:1313" class="iconfont icon-github" title="github"></a>
      <a href="http://localhost:1313" class="iconfont icon-weibo" title="weibo"></a>
      <a href="http://localhost:1313" class="iconfont icon-zhihu" title="zhihu"></a>
      <a href="http://localhost:1313" class="iconfont icon-douban" title="douban"></a>
      <a href="http://localhost:1313" class="iconfont icon-pocket" title="pocket"></a>
      <a href="http://localhost:1313" class="iconfont icon-tumblr" title="tumblr"></a>
      <a href="http://localhost:1313" class="iconfont icon-instagram" title="instagram"></a>
      <a href="http://localhost:1313" class="iconfont icon-gitlab" title="gitlab"></a>
      <a href="http://localhost:1313" class="iconfont icon-bilibili" title="bilibili"></a>
  <a href="https://xiongshou.github.io/index.xml" type="application/rss+xml" class="iconfont icon-rss" title="rss"></a>
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - 
    <a class="theme-link" href="https://github.com/olOwOlo/hugo-theme-even">Even</a>
  </span>

  

  <span class="copyright-year">
    &copy; 
    2017 - 
    2021<span class="heart"><i class="iconfont icon-heart"></i></span><span>olOwOlo</span>
  </span>
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont icon-up"></i>
    </div>
  </div>
  
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.2.1/dist/jquery.min.js" integrity="sha256-hwg4gsxgFZhOsEEamdOYGBf13FyQuiTwlAQgxVSNgt4=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/slideout@1.0.1/dist/slideout.min.js" integrity="sha256-t+zJ/g8/KXIJMjSVQdnibt4dlaDxc9zXr/9oNPeWqdg=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.js" integrity="sha256-XVLffZaxoWfGUEbdzuLi7pwaUJv1cecsQJQqGLe7axY=" crossorigin="anonymous"></script>



<script type="text/javascript" src="/js/main.min.c99b103c33d1539acf3025e1913697534542c4a5aa5af0ccc20475ed2863603b.js"></script>








</body>
</html>
